

public class Evaluator {

	public static Environment THE_GLOBAL_ENVIRONMENT = new Environment();
	public static final Data THE_EMPTY_LIST = new Null();
	public static final Data NO_VALUE = new Atom("okay");
	public static final Data COMMENT = new Atom("");
	public static final SchavaBoolean SCHAVA_FALSE = new SchavaBoolean(false);
	public static final SchavaBoolean SCHAVA_TRUE = new SchavaBoolean(true);

	public static Data eval(Data data, Environment env) {
		return eval(data, env, false);
	}
		
	public static Data eval(Data data, Environment env, boolean force) {
		// TODO car cadr, etc
		Data toReturn;
		do {
			if (data.isThunk()) {
				env = data.getThunkEnv();
				data = data.getThunkExp();
				toReturn = data;
			}
			
			if (data.isEmpty()) {
				toReturn = NO_VALUE;
			} else if (data.isSelfEvaluating()) {
				toReturn = data;
			} else if (data.isProcedure()) {
				toReturn = data;
			} else if (data.isQuoted()) {
				toReturn = data.textOfQuotation();
			} else if (data.isVariable()) {
				toReturn = env.lookupVariable(data.toString());
			} else if (data.isSetCar()) {
				toReturn = evalSetCar(data, env);
			} else if (data.isSetCdr()) {
				toReturn = evalSetCdr(data, env);
			} else if (data.isAssignment()) {
				toReturn = evalAssignment(data, env);
			} else if (data.isDefinition()) {
				toReturn = evalDefinition(data, env);
			} else if (data.isIf()) {
				toReturn = evalIf(data, env);
			} else if (data.isCond()) {
				toReturn = evalCond(data, env);
			} else if (data.isLet()) {
				toReturn = evalLet(data, env);
			} else if (data.isLambda()) {
				toReturn = evalLambda(data, env);
			} else if (data.isBegin()) {
				toReturn = evalSequence(data.beginActions(), env);
			} else if (data.isApply()) {
				toReturn = evalApply(data, env);
			} else if (data.isApplication()) {
				if (force) {
					// This is the normal application
					toReturn = schavaApply(eval(data.operator(), env),
							listOfValues(data.operands(), env));
				} else {
					// We can delay the application.
					// This may be the end result of a deeper
					// call to eval, which means that we can pass 
					// "instructions" back up to the caller about
					// how to evaluate this data in this environment.
					toReturn = makeThunk(data, env);
				}
			} else {
				throw new SchavaException("Unknown expression: " + data);
			}
			data = toReturn;
		} while (force && toReturn.isThunk());
		return toReturn;
	}

	
	public static Data makeThunk(Data _expression, Environment _env) {
		return Primitive.cons("thunk", 
				Primitive.cons(_expression, 
						Primitive.cons(_env, Evaluator.THE_EMPTY_LIST)));
	}
	
	private static Data listOfValues(Data operands, Environment env) {
		if (operands.isNull()) {
			return Evaluator.THE_EMPTY_LIST;
		} else {
			// Force it
			return Primitive.cons(eval(operands.car(), env, true), listOfValues(operands.cdr(), env));
		}
	}

	public static Data schavaApply(Data _procedure, Data arguments) {
		if (!(_procedure instanceof Procedure)) {
			throw new SchavaException("apply: argument not a procedure");
		}
		Procedure procedure = (Procedure) _procedure;
		if (procedure.isPrimitiveProcedure()) {
			return Primitive.applyPrimitive(procedure, arguments);
		} else if (procedure.isCompoundProcedure()) {
			return applyCompound(procedure, arguments);
		} else {
			throw new SchavaException("schavaApply: Unknown procedure.");
		}
	}


	public static Data applyCompound(Procedure procedure, Data arguments) {
		Data params = procedure.getLetParameters();
		Data bodySequence = procedure.getBodySequence();
		Environment env = procedure.getEnvironment();
		Environment newEnv = new Environment(params, arguments, env);

		return evalSequence(bodySequence, newEnv);
	}



	public static Data evalIf(Data data, Environment env) {
		Pair ifObject = (Pair) data;
		// Force it
		if (eval(ifObject.ifClause(), env, true).isTrue()) {
			// Thunk it
			return eval(ifObject.trueClause(), env);
		} else {
			// Thunk it
			return eval(ifObject.elseClause(), env);
		}
	}

	public static Data evalCond(Data data, Environment env) {
		return eval(condToIf(data), env);
	}

	public static Data evalLet(Data data, Environment env) {
		Data bindings = data.letBindings();
		Data body = data.letBodySequence();
		Data listOfParameters = bindings.getLetParameters();
		Data listOfArguments = bindings.getLetArguments();
		Data listOfValues = listOfValues(listOfArguments, env);
		Data proc = new Procedure(listOfParameters, body, env);
		Data expression = Primitive.cons(proc, listOfValues);
		// Thunk it
		return eval(expression, env);
	}

	public static Data condToIf(Data data) {
		return expandClauses(data.condClauses());
	}

	public static Data expandClauses(Data clauses) {
		if (clauses.isNull()) {
			return SCHAVA_FALSE;
		} else {
			Data firstClause = clauses.car();
			Data rest = clauses.cdr();
			if (firstClause.isElseClause()) {
				if (rest.isNull()) {
					return firstClause.condActions().sequenceToExpression();
				} else {
					throw new SchavaException("Else clause is not last " +
							"in COND statement: " + clauses.toString());
				}
			} else {
				return makeIf(firstClause.condPredicate(),
						firstClause.condActions().sequenceToExpression(),
						expandClauses(rest));
			}
		}
	}


	public static Data makeIf(Data predicate, Data trueClause, Data falseClause) {
		return Primitive.cons("if",
				Primitive.cons(predicate, 
						Primitive.cons(trueClause, 
								Primitive.cons(falseClause, Evaluator.THE_EMPTY_LIST))));
	}



	public static Data evalDefinition(Data data, Environment env) {
		if (Primitive.length(data) >= 3) {
			String variableName;
			Data variable = data.getAssignmentVariable();

			if (variable.isPair()) { // Procedure
				variableName = variable.car().toString();
				Data parameters = variable.cdr();
				Data bodySequence = data.getLambdaBodySequence();
				Procedure newProc = new Procedure(parameters, bodySequence, env);
				env.makeAssignment(variableName, newProc);
				return NO_VALUE;
			} else {
				// Force it
				Data value = eval(data.getAssignmentArgument(), env, true);
				variableName = variable.toString();
				env.makeAssignment(variableName, value);
				return NO_VALUE;	
			}
		}
		throw new SchavaException("define: expects 2 arguments");
	}

	public static Data evalLambda(Data data, Environment env) {
		if (Primitive.length(data) >= 3) {
			Data parameters = data.cdr().car();
			Data sequence = data.cdr().cdr();
			return new Procedure(parameters, sequence, env);
		} else {
			throw new SchavaException("lambda: expects 2 arguments");
		}
	}

	public static Data evalAssignment(Data data, Environment env) {
		if (Primitive.length(data) == 3) {
			// Force it
			env.setVariableValue(data.cdr().car().toString(), 
					eval(data.cdr().cdr().car(), env, true));
		}
		return NO_VALUE;
	}

	public static Data evalSetCar(Data data, Environment env) {
		if (Primitive.length(data) == 3) {
			// Force it
			Pair toSet = (Pair) eval(data.cdr().car(), env, true);
			toSet.setCar(eval(data.cdr().cdr().car(), env, true));
			return NO_VALUE;
		}
		return NO_VALUE;
	}

	public static Data evalSetCdr(Data data, Environment env) {
		if (Primitive.length(data) == 3) {
			// Force it
			Pair toSet = (Pair) eval(data.cdr().car(), env, true);
			toSet.setCdr(eval(data.cdr().cdr().car(), env, true));
			return NO_VALUE;
		}
		return NO_VALUE;
	}

	public static Data evalSequence(Data data, Environment env) {
		if (Primitive.length(data) == 1) {
			// Thunk it
			return eval(data.car(), env);
		} else {
			// Force it
			eval(data.car(), env, true);
			return evalSequence(data.cdr(), env);
		}
	}

	public static Data evalApply(Data data, Environment env) {
		// Force it
		Data op = eval(data.getApplyOp(), env, true);
		Data exp = eval(data.getApplyExp(), env, true);
		return schavaApply(op, exp);
	}


	public static void initializeScheme() {
		Evaluator.THE_GLOBAL_ENVIRONMENT.makeAssignments(Primitive.getPrimitives());

	}


	public static void main(String [] args) {
		System.out.println("Initializing Scheme...");
		initializeScheme();
		System.out.println("Starting evaluator.");
		InputSource lines = new InputSource();
		repl(lines);
	}

	public static void repl(InputSource lines) {

		String line = "";
		Data inputData;
		Data input = null;
		Data output;
		System.out.print("> ");
		while (!line.equals("quit")) {
			do {
				line += lines.readLine();
			} while (line.length() == 0);
			output = null;
			try {
				while (line.length() > 0) {
					inputData = Parser.parse(line);
					input = inputData.car();
					line = inputData.cdr().toString();
					if (input != COMMENT) {
						// Force it
						output = eval(input, THE_GLOBAL_ENVIRONMENT, true); // Be sure to force the answer.
						System.out.println(output);
					}
				}
				System.out.print("> ");
			} catch (SchavaException e) {
				System.err.println(e);
				line = "";
				System.out.print("\n> ");
			} catch (UnfinishedLineException e) {
			}

		}
	}



}
